/*
 * CS202 Spring 2009
 * Professor: Dr. Michael Peterson
 * Student: Deylo Woo dwoo711@gmail.com
 */
/*
 * This class contains a basic implementation of a tree that only stores
 * integers.  Some methods below are completely implemented below; you will need
 * to provide implementations of the remaining methods (see the comments below
 * and the project description).  You will also have to reimplement the entire
 * class to create a generics-based tree that can store any type of object (see
 * the project description).
 * 
 * This class implements a tree using the TreeNode class.  It relies heavily
 * on recursion.  This tree can only contain integers.
 * 
 * This class is based upon the Tree class in chapter 17 of Java: How
 * to Program 7th ed. (Deitel & Deitel).
 */
package project2;

import java.util.Random;

/**
 *
 * @author Michael R. Peterson, based upon Deitel & Deitel 
 */
public class IntTree {

    private TreeNode root;

    // constructor initialized an empty Tree of integers
    public IntTree() {
        root = null;
    }

    // insert a new node in the binary search tree
    public void insertNode(int insertValue) {
        if (root == null) {
            // create root value here
            root = new TreeNode(insertValue, root);
        } else {
            // call the root node's insert value
            root.insert(insertValue, root);
        }
    } // end method insertValue

    /**
     * Prints the contents of the tree in a preorder traversal.
     */
    public void preorderTraversal() {
        preorderHelper(root);
    }

    /**
     * Conduct a recursive sequential traversal of our tree:
     * - Print the current node.
     * - Traverse the left subtree (if it exists)
     * - Traverse the right subtree (if it exists)
     * @param node the current node in our traversal.
     */
    private void preorderHelper(TreeNode node) {
        if (node == null) {
            return;
        }

        System.out.printf("%d ", node.data); // output data
        preorderHelper(node.leftNode);      // left traversal
        preorderHelper(node.rightNode);     // right traversal
    } // end method preorderHelper

    /**
     * Prints the contents of the tree in a sequential traversal.
     */
    public void inorderTraversal() {
        inorderHelper(root);
    }

    /**
     * Conduct a recursive sequential traversal of our tree:
     * - Traverse the left subtree (if it exists)
     * - Print the current node.
     * - Traverse the right subtree (if it exists)
     * @param node the current node in our traversal.
     */
    private void inorderHelper(TreeNode node) {
        if (node == null) {
            return;
        }

        inorderHelper(node.leftNode);      // left traversal
        System.out.printf("%d ", node.data); // output data
        inorderHelper(node.rightNode);     // right traversal
    } // end method inorderHelper

    /**
     * Prints the contents of the tree in a postorder traversal.
     */
    public void postorderTraversal() {
        postorderHelper(root);
    }

    /**
     * Conduct a recursive postorder traversal of our tree:
     * - Traverse the left subtree (if it exists)
     * - Traverse the right subtree (if it exists)
     * - Print the current node.
     * @param node the current node in our traversal.
     */
    private void postorderHelper(TreeNode node) {
        // base case, we are at a null node
        if (node == null) {
            return;
        }

        // rec. case: traverse the tree
        postorderHelper(node.leftNode);      // left traversal
        postorderHelper(node.rightNode);     // right traversal
        System.out.printf("%d ", node.data); // output data
    } // end method postorderHelper

    /**
     * Calculate the number of nodes in this tree.
     * @return Number of nodes in the tree.
     */
    public int size() {
        if (root == null) {
            return 0;
        }
        return sizeHelper(root);
    }

    // Recursive method to assist our size method.  Counts the number
    // of nodes in the tree via a recursive traversal of the tree.
    private int sizeHelper(TreeNode node) {
        // base case: the current node is null
        if (node == null) {
            return 0;
        }
        // recursive case: add the size of each subtree to 1 to count
        // the current node, and return the result.
        return 1 + sizeHelper(node.leftNode) + sizeHelper(node.rightNode);
    }

    /**
     * Generate a string containing an inorder listing of the numbers in the
     * tree.
     * @return inorder listing of the tree contents.
     */
    public String toString() {
        if (root == null) {
            return new String("Tree is empty.");
        }
        return stringHelper(root);
    }

    // helper function to recursively build a string representation of the
    // tree's contents - uses a recursive inorder traversal.
    private String stringHelper(TreeNode node) {
        if (node == null) {
            return null;
        }

        String s1 = stringHelper(node.leftNode);
        String s2 = new Integer(node.data).toString();
        String s3 = stringHelper(node.rightNode);

        StringBuilder s = new StringBuilder();
        if (s1 != null) {
            s.append(s1 + " ");
        }
        s.append(s2);
        if (s3 != null) {
            s.append(" " + s3);
        }
        return s.toString();

    }

    /*----------------------------------------------------------------------
     * YOU MUST PROVIDE COMPLETE IMPLEMENTATIONS OF THE METHODS BELOW.
     * IN SOME CASES, YOU MAY WISH TO IMPLEMENT HELPER METHODS AS SHOWN
     * WITH THE TRAVERSAL METHODS SHOWN ABOVE.
     * ---------------------------------------------------------------------*/
    /**
     * Prints the contents of the tree in a reverse order traversal (showing
     * elements in highest to lowest order.
     */
    public void reverseorderTraversal() {
        reverseorderHelper(root);
    }

    /**
     * Traverses in reverse order going from highest value on
     * on right side of the tree to lowest on the left
     * @param node: recursive node
     */
    private void reverseorderHelper(TreeNode node) {
        if (node == null) {
            return;
        }

        reverseorderHelper(node.rightNode);
        System.out.printf("%d ", node.data);
        reverseorderHelper(node.leftNode);
    }

    /**
     * Determine the depth of the tree: How many layers deep does it go?
     * For example - A tree with a single node has depth 0.  A tree with
     * two leaf nodes coming off the root node has depth 1.  If one of those
     * leaves instead had a leaf coming off of it, the tree would have depth 2,
     * and so on.
     * @return The depth of the tree.
     */
    public int depth() {
        return depthHelper(root);
    }

    /**
     * finds the depth by by going to all possible paths to leaf and keeping track
     * of longest path by returning it
     * @param node: recursive  node
     * @return: longest path from root to leaf
     */
    private int depthHelper(TreeNode node) {
        int _rightDepth = 0;
        int _leftDepth = 0;

        if (node == null) {
            return 0;
        }
        _leftDepth = depthHelper(node.leftNode) + 1;
        _rightDepth = depthHelper(node.rightNode) + 1;

        //return the longest depth of a subTree
        if (_leftDepth > _rightDepth) {
            return _leftDepth;
        } else {
            return _rightDepth;
        }
    }

    /**
     * Returns true if the given number is in the tree, returns false otherwise.
     * Note: this method DOES NOT insert the number into the tree
     * @param num The number to check.
     * @return true if the number is present, false otherwise.
     */
    public boolean numberInTree(int num) {
        return numberInTreeHelper(root, num);
    }

    /**
     * Finds a number in a tree and returns true, false otherwise.
     * @param node: recursive node
     * @param num: num to find
     * @return: true or false based on find
     */
    private boolean numberInTreeHelper(TreeNode node, int num) {

        if (node == null) {
            return false;
        }

        if (node.data == num) {
            return true;
        } else if (num > node.data) {
            return numberInTreeHelper(node.rightNode, num);
        } else {
            return numberInTreeHelper(node.leftNode, num);
        }
    }

    /**
     * Finds and returns (without removing) the maximum value in the tree.
     * if the tree is empty, return the constant Integer.MIN_VALUE, rather than
     * throwing an exception.
     * @return The maximum value present in the tree.
     */
    public int max() {
        return maxHelper(root);
    }

    /**
     * find the max value by going down the right tree
     * @param node: recursive node
     * @return: int value with max data value
     */
    private int maxHelper(TreeNode node) {
        if (node == null) {
            return Integer.MIN_VALUE;
        } else if (node.rightNode == null) {
            return node.data;
        } else {
            return maxHelper(node.rightNode);
        }
    }

    /**
     * Finds and returns (without removing) the minimum value in the tree.
     * if the tree is empty, return the constant Integer.MAX_VALUE, rather than
     * throwing an exception.
     * @return The minimum value present in the tree.
     */
    public int min() {
        return minHelper(root);
    }

    /**
     * find the min value by going down the left subtree
     * @param node: recursive node
     * @return: return in min value
     */
    private int minHelper(TreeNode node) {
        if (node == null) {
            return Integer.MAX_VALUE;
        } else if (node.leftNode == null) {
            return node.data;
        } else {
            return minHelper(node.leftNode);
        }
    }

    /**
     * If num is in the tree, remove it from the tree, taking care to 
     * restructure the tree properly if necessary.  If the number is not
     * present, no action is taken.
     * NOTE: By a large margin, this will be the most difficult method for
     * you to implement.  See a description of the removal operation in the
     * project description.
     * @param num The number to remove from the tree.
     */
    public void remove(int num) {
        removeHelper(root, num);
    }

    /**
     * Spent a lot of time here but I got it.
     * It removes from a node based on value passed
     * in the parameter.
     * @param node: recursive node
     * @param num: value of node to be deleted
     */
    private void removeHelper(TreeNode node, int num) {
        if (node == null) {
            return;
        }
        //balance search tree, find which subtree value could be
        if (num > node.data && node.rightNode != null) {
            removeHelper(node.rightNode, num);
        } else if (num < node.data && node.leftNode != null) {
            removeHelper(node.leftNode, num);
        } else {//data matches num
            if (node.leftNode == null && node.rightNode == null) {//leaf, just set to null
                TreeNode parentNode = node.parentNode;
                node.parentNode = null;
                if (parentNode.leftNode != null) {
                    parentNode.leftNode = null;
                }
                if (parentNode.rightNode != null) {
                    parentNode.rightNode = null;
                }
                return;
            } else if (node.leftNode == null) {//has right child
                node.data = new Integer(node.rightNode.data);
                node.rightNode = null;
                return;
            } else if (node.rightNode == null) {//has left child
                node.data = new Integer(node.leftNode.data);
                node.leftNode = null;
                return;
            } else {//has two nodes
                TreeNode _minN = minNode(node.rightNode);//find the min value on right subTree
                node.data = new Integer(_minN.data);//replace data
                removeHelper(_minN, _minN.data);//remove min again
                return;
            }
        }
    }

    /**
     * Helper method to find and return the min node which is farthest on the left.
     * @param node: recursive node
     * @return: return min node
     */
    private TreeNode minNode(TreeNode node) {
        if (node == null) {
            return null;
        } else if (node.leftNode == null) {
            return node;
        } else {
            return minNode(node.leftNode);
        }
    }

    /*----------------------------------------------------------------------
     * END OF METHODS THAT YOU MUST IMPLEMENT
     * ---------------------------------------------------------------------*/
    /**
     * Test code for IntTree.java
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here

        // The code below randomly adds 20 numbers randomly chosen between 0 and
        // 100.  We then test our various traversal methods.

        System.out.println("IntTree Test Code:");
        System.out.println("Adding 20 random numbers...");
        Random rand = new Random();
        IntTree tree = new IntTree();
        for (int i = 0; i < 20; i++) {
            tree.insertNode(rand.nextInt(101));
        }

//        for (int i = 1; i <=
//                20; i++) {
//            tree.insertNode(i);
//        }

        System.out.println("\n\nTree preorder traversal:\n");
        tree.preorderTraversal();

        System.out.println("\n\nTree postorder traversal:\n");
        tree.postorderTraversal();

        System.out.println("\n\nTree inorder traversal:\n");
        tree.inorderTraversal();

        System.out.println("\n\nTesting tree's toString (uses an inorder traversal):");
        System.out.println(tree);

        // test the size method
        System.out.println("\n\nThe tree has " + tree.size() + " nodes.");

        System.out.println("\n\nTesting tree's reverse order traversal");
        tree.reverseorderTraversal();

        System.out.println("\n\nTree depth: " + tree.depth() + "\n\n");


        System.out.println("Loop from  1 - 100 to match\n");
        for (int i = 1; i <= 100; i++) {
            System.out.println("Is number " + i + " in Tree?: " + tree.numberInTree(i));
        }

        System.out.println("\n\nThe Max is: " + tree.max());

        System.out.println("\n\nThe Min is: " + tree.min());

        IntTree tree2 = new IntTree();

        tree2.insertNode(30);
        tree2.insertNode(10);
        tree2.insertNode(15);
        tree2.insertNode(45);
        tree2.insertNode(12);
        tree2.insertNode(8);
        tree2.insertNode(59);
        tree2.insertNode(78);
        tree2.insertNode(13);

        System.out.println("\n\nTree2 preorder traversal:\n");
        tree2.preorderTraversal();

        System.out.println("\n\nTree2 postorder traversal:\n");
        tree2.postorderTraversal();

        System.out.println("\n\nTree2 inorder traversal:\n");
        tree2.inorderTraversal();

        System.out.println("\n\nTree2 remove 10 (node with children):");
        tree2.remove(10);

        System.out.println("\n\nTree2 preorder traversal:\n");
        tree2.preorderTraversal();

        System.out.println("\n\nTree2 postorder traversal:\n");
        tree2.postorderTraversal();

        System.out.println("\n\nTree2 inorder traversal:\n");
        tree2.inorderTraversal();

        System.out.println("\n\nTree2 remove 78 (leaf node):");
        tree2.remove(78);

        System.out.println("\n\nTree2 preorder traversal:\n");
        tree2.preorderTraversal();

        System.out.println("\n\nTree2 postorder traversal:\n");
        tree2.postorderTraversal();

        System.out.println("\n\nTree2 inorder traversal:\n");
        tree2.inorderTraversal();


//        System.out.println("\n\nTree2 remove 12:");
//        tree2.remove(12);
//
//        System.out.println("\n\nTree2 preorder traversal:\n");
//        tree2.preorderTraversal();
//
//        System.out.println("\n\nTree2 postorder traversal:\n");
//        tree2.postorderTraversal();
//
//        System.out.println("\n\nTree2 inorder traversal:\n");
//        tree2.inorderTraversal();

    }
}
